home *** CD-ROM | disk | FTP | other *** search
/ Young Minds / Young Minds Interactive CD-ROM.ISO / backgamm / move.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-03-09  |  10.9 KB  |  532 lines
  1. /*
  2.  * Copyright (c) 1980 Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms are permitted
  6.  * provided that this notice is preserved and that due credit is given
  7.  * to the University of California at Berkeley. The name of the University
  8.  * may not be used to endorse or promote products derived from this
  9.  * software without specific prior written permission. This software
  10.  * is provided ``as is'' without express or implied warranty.
  11.  */
  12.  
  13. #ifndef lint
  14. static char sccsid[] = "@(#)move.c    5.3 (Berkeley) 2/16/88";
  15. #endif /* not lint */
  16.  
  17. #include "back.h"
  18.  
  19. #ifdef DEBUG
  20. #include <stdio.h>
  21. FILE    *trace;
  22. static char    tests[20];
  23. #endif
  24.  
  25. struct BOARD  {                /* structure of game position */
  26.     int    b_board[26];            /* board position */
  27.     int    b_in[2];            /* men in */
  28.     int    b_off[2];            /* men off */
  29.     int    b_st[4], b_fn[4];        /* moves */
  30.  
  31.     struct BOARD    *b_next;        /* forward queue pointer */
  32. };
  33.  
  34. struct BOARD *freeq = 0;
  35. struct BOARD *checkq = 0;
  36. struct BOARD *bsave();
  37. struct BOARD *nextfree();
  38.  
  39.                     /* these variables are values for the
  40.                      * candidate move */
  41. static int    ch;                /* chance of being hit */
  42. static int    op;                /* computer's open men */
  43. static int    pt;                /* comp's protected points */
  44. static int    em;                /* farthest man back */
  45. static int    frc;                /* chance to free comp's men */
  46. static int    frp;                /* chance to free pl's men */
  47.  
  48.                     /* these values are the values for the
  49.                      * move chosen (so far) */
  50. static int    chance;                /* chance of being hit */
  51. static int    openmen;            /* computer's open men */
  52. static int    points;                /* comp's protected points */
  53. static int    endman;                /* farthest man back */
  54. static int    barmen;                /* men on bar */
  55. static int    menin;                /* men in inner table */
  56. static int    menoff;                /* men off board */
  57. static int    oldfrc;                /* chance to free comp's men */
  58. static int    oldfrp;                /* chance to free pl's men */
  59.  
  60. static int    cp[5];                /* candidate start position */
  61. static int    cg[5];                /* candidate finish position */
  62.  
  63. static int    race;                /* game reduced to a race */
  64.  
  65. move (okay)
  66. int    okay;                    /* zero if first move */
  67. {
  68.     register int    i;        /* index */
  69.     register int    l;        /* last man */
  70.  
  71.     if (okay)  {
  72.                         /* see if comp should double */
  73.         if (gvalue < 64 && dlast != cturn && dblgood())  {
  74.             writel (*Colorptr);
  75.             dble();                /* double */
  76.                             /* return if declined */
  77.             if (cturn != 1 && cturn != -1)
  78.                 return;
  79.         }
  80.         roll();
  81.     }
  82.  
  83.     race = 0;
  84.     for (i = 0; i < 26; i++)  {
  85.         if (board[i] < 0)
  86.             l = i;
  87.     }
  88.     for (i = 0; i < l; i++)  {
  89.         if (board[i] > 0)
  90.             break;
  91.     }
  92.     if (i == l)
  93.         race = 1;
  94.  
  95.                         /* print roll */
  96.     if (tflag)
  97.         curmove (cturn == -1? 18: 19,0);
  98.     writel (*Colorptr);
  99.     writel (" rolls ");
  100.     writec (D0+'0');
  101.     writec (' ');
  102.     writec (D1+'0');
  103.                         /* make tty interruptable
  104.                          * while thinking */
  105.     if (tflag)
  106.         cline();
  107.     fixtty (noech);
  108.  
  109.                         /* find out how many moves */
  110.     mvlim = movallow();
  111.     if (mvlim == 0)  {
  112.         writel (" but cannot use it.\n");
  113.         nexturn();
  114.         fixtty (raw);
  115.         return;
  116.     }
  117.  
  118.                         /* initialize */
  119.     for (i = 0; i < 4; i++)
  120.         cp[i] = cg[i] = 0;
  121.  
  122.                         /* strategize */
  123.     trymove (0,0);
  124.     pickmove();
  125.  
  126.                         /* print move */
  127.     writel (" and moves ");
  128.     for (i = 0; i < mvlim; i++)  {
  129.         if (i > 0)
  130.             writec (',');
  131.         wrint (p[i] = cp[i]);
  132.         writec ('-');
  133.         wrint (g[i] = cg[i]);
  134.         makmove (i);
  135.     }
  136.     writec ('.');
  137.  
  138.                         /* print blots hit */
  139.     if (tflag)
  140.         curmove (20,0);
  141.     else
  142.         writec ('\n');
  143.     for (i = 0; i < mvlim; i++)
  144.         if (h[i])
  145.             wrhit(g[i]);
  146.                         /* get ready for next move */
  147.     nexturn();
  148.     if (!okay)  {
  149.         buflush();
  150.         sleep (3);
  151.     }
  152.     fixtty (raw);                /* no more tty interrupt */
  153. }
  154.  
  155. trymove (mvnum,swapped)
  156. register int    mvnum;                /* number of move (rel zero) */
  157. int        swapped;            /* see if swapped also tested */
  158.  
  159. {
  160.     register int    pos;            /* position on board */
  161.     register int    rval;            /* value of roll */
  162.  
  163.                         /* if recursed through all dice
  164.                          * values, compare move */
  165.     if (mvnum == mvlim)  {
  166.         binsert (bsave());
  167.         return;
  168.     }
  169.  
  170.                         /* make sure dice in always
  171.                          * same order */
  172.     if (d0 == swapped)
  173.         swap;
  174.                         /* choose value for this move */
  175.     rval = dice[mvnum != 0];
  176.  
  177.                         /* find all legitimate moves */
  178.     for (pos = bar; pos != home; pos += cturn)  {
  179.                         /* fix order of dice */
  180.         if (d0 == swapped)
  181.             swap;
  182.                         /* break if stuck on bar */
  183.         if (board[bar] != 0 && pos != bar)
  184.             break;
  185.                         /* on to next if not occupied */
  186.         if (board[pos]*cturn <= 0)
  187.             continue;
  188.                         /* set up arrays for move */
  189.         p[mvnum] = pos;
  190.         g[mvnum] = pos+rval*cturn;
  191.         if (g[mvnum]*cturn >= home)  {
  192.             if (*offptr < 0)
  193.                 break;
  194.             g[mvnum] = home;
  195.         }
  196.                         /* try to move */
  197.         if (makmove (mvnum))
  198.             continue;
  199.         else
  200.             trymove (mvnum+1,2);
  201.                         /* undo move to try another */
  202.         backone (mvnum);
  203.     }
  204.  
  205.                         /* swap dice and try again */
  206.     if ((!swapped) && D0 != D1)
  207.         trymove (0,1);
  208. }
  209.  
  210. struct BOARD *
  211. bsave ()  {
  212.     register int    i;        /* index */
  213.     struct BOARD    *now;        /* current position */
  214.  
  215.     now = nextfree ();        /* get free BOARD */
  216.  
  217.                     /* store position */
  218.     for (i = 0; i < 26; i++)
  219.         now->b_board[i] = board[i];
  220.     now->b_in[0] = in[0];
  221.     now->b_in[1] = in[1];
  222.     now->b_off[0] = off[0];
  223.     now->b_off[1] = off[1];
  224.     for (i = 0; i < mvlim; i++)  {
  225.         now->b_st[i] = p[i];
  226.         now->b_fn[i] = g[i];
  227.     }
  228.     return (now);
  229. }
  230.  
  231. binsert (new)
  232. struct BOARD    *new;                    /* item to insert */
  233. {
  234.     register struct BOARD    *p = checkq;        /* queue pointer */
  235.     register int        result;            /* comparison result */
  236.  
  237.     if (p == 0)  {                /* check if queue empty */
  238.         checkq = p = new;
  239.         p->b_next = 0;
  240.         return;
  241.     }
  242.  
  243.     result = bcomp (new,p);            /* compare to first element */
  244.     if (result < 0)  {                /* insert in front */
  245.         new->b_next = p;
  246.         checkq = new;
  247.         return;
  248.     }
  249.     if (result == 0)  {                /* duplicate entry */
  250.         mvcheck (p,new);
  251.         makefree (new);
  252.         return;
  253.     }
  254.  
  255.     while (p->b_next != 0)  {        /* traverse queue */
  256.         result = bcomp (new,p->b_next);
  257.         if (result < 0)  {            /* found place */
  258.             new->b_next = p->b_next;
  259.             p->b_next = new;
  260.             return;
  261.         }
  262.         if (result == 0)  {            /* duplicate entry */
  263.             mvcheck (p->b_next,new);
  264.             makefree (new);
  265.             return;
  266.         }
  267.         p = p->b_next;
  268.     }
  269.                         /* place at end of queue */
  270.     p->b_next = new;
  271.     new->b_next = 0;
  272. }
  273.  
  274. bcomp (a,b)
  275. struct BOARD    *a;
  276. struct BOARD    *b;
  277. {
  278.     register int    *aloc = a->b_board;    /* pointer to board a */
  279.     register int    *bloc = b->b_board;    /* pointer to board b */
  280.     register int    i;            /* index */
  281.     int        result;            /* comparison result */
  282.  
  283.     for (i = 0; i < 26; i++)  {        /* compare boards */
  284.         result = cturn*(aloc[i]-bloc[i]);
  285.         if (result)
  286.             return (result);        /* found inequality */
  287.     }
  288.     return (0);                /* same position */
  289. }
  290.  
  291. mvcheck (incumbent,candidate)
  292. register struct BOARD     *incumbent;
  293. register struct BOARD     *candidate;
  294. {
  295.     register int    i;
  296.     register int    result;
  297.  
  298.     for (i = 0; i < mvlim; i++)  {
  299.         result = cturn*(candidate->b_st[i]-incumbent->b_st[i]);
  300.         if (result > 0)
  301.             return;
  302.         if (result < 0)
  303.             break;
  304.     }
  305.     if (i == mvlim)
  306.         return;
  307.     for (i = 0; i < mvlim; i++)  {
  308.         incumbent->b_st[i] = candidate->b_st[i];
  309.         incumbent->b_fn[i] = candidate->b_fn[i];
  310.     }
  311. }
  312.  
  313. makefree (dead)
  314. struct BOARD    *dead;            /* dead position */
  315. {
  316.     dead->b_next = freeq;            /* add to freeq */
  317.     freeq = dead;
  318. }
  319.  
  320. struct BOARD *
  321. nextfree ()  {
  322.     struct BOARD    *new;
  323.  
  324.     if (freeq == 0)  {
  325.         new = (struct BOARD *)calloc (1,sizeof (struct BOARD));
  326.         if (new == 0)  {
  327.             writel ("\nOut of memory\n");
  328.             getout();
  329.         }
  330.         new->b_next = 0;
  331.         return (new);
  332.     }
  333.  
  334.     new = freeq;
  335.     freeq = freeq->b_next;
  336.     return new;
  337. }
  338.  
  339. pickmove ()  {
  340.                         /* current game position */
  341.     register struct BOARD    *now = bsave();
  342.     register struct BOARD    *next;        /* next move */
  343.  
  344. #ifdef DEBUG
  345.     if (trace == NULL)
  346.         trace = fopen ("bgtrace","w");
  347.     fprintf (trace,"\nRoll:  %d %d%s\n",D0,D1,race? " (race)": "");
  348.     fflush (trace);
  349. #endif
  350.     do  {                /* compare moves */
  351.         bcopy (checkq);
  352.         next = checkq->b_next;
  353.         makefree (checkq);
  354.         checkq = next;
  355.         movcmp();
  356.     } while (checkq != 0);
  357.  
  358.     bcopy (now);
  359. }
  360.  
  361. bcopy (s)
  362. register struct BOARD    *s;            /* game situation */
  363. {
  364.     register int    i;            /* index */
  365.  
  366.     for (i = 0; i < 26; i++)
  367.         board[i] = s->b_board[i];
  368.     for (i = 0; i < 2; i++)  {
  369.         in[i] = s->b_in[i];
  370.         off[i] = s->b_off[i];
  371.     }
  372.     for (i = 0; i < mvlim; i++)  {
  373.         p[i] = s->b_st[i];
  374.         g[i] = s->b_fn[i];
  375.     }
  376. }
  377.  
  378. movcmp ()  {
  379.     register int    i;
  380.     register int    c;
  381.  
  382. #ifdef DEBUG
  383.     if (trace == NULL)
  384.         trace = fopen ("bgtrace","w");
  385. #endif
  386.  
  387.     odds (0,0,0);
  388.     if (!race)  {
  389.         ch = op = pt = 0;
  390.         for (i = 1; i < 25; i++)  {
  391.             if (board[i] == cturn)
  392.                 ch = canhit (i,1);
  393.                 op += abs (bar-i);
  394.         }
  395.         for (i = bar+cturn; i != home; i += cturn)
  396.             if (board[i]*cturn > 1)
  397.                 pt += abs(bar-i);
  398.         frc = freemen (bar)+trapped (bar,cturn);
  399.         frp = freemen (home)+trapped (home,-cturn);
  400.     }
  401.     for (em = bar; em != home; em += cturn)
  402.         if (board[em]*cturn > 0)
  403.             break;
  404.     em = abs(home-em);
  405. #ifdef DEBUG
  406.     fputs ("Board: ",trace);
  407.     for (i = 0; i < 26; i++)
  408.         fprintf (trace, " %d",board[i]);
  409.     if (race)
  410.         fprintf (trace,"\n\tem = %d\n",em);
  411.     else
  412.         fprintf (trace,
  413.             "\n\tch = %d, pt = %d, em = %d, frc = %d, frp = %d\n",
  414.             ch,pt,em,frc,frp);
  415.     fputs ("\tMove: ",trace);
  416.     for (i = 0; i < mvlim; i++)
  417.         fprintf (trace," %d-%d",p[i],g[i]);
  418.     fputs ("\n",trace);
  419.     fflush (trace);
  420.     strcpy (tests,"");
  421. #endif
  422.     if ((cp[0] == 0 && cg[0] == 0) || movegood())  {
  423. #ifdef DEBUG
  424.         fprintf (trace,"\t[%s] ... wins.\n",tests);
  425.         fflush (trace);
  426. #endif
  427.         for (i = 0; i < mvlim; i++)  {
  428.             cp[i] = p[i];
  429.             cg[i] = g[i];
  430.         }
  431.         if (!race)  {
  432.             chance = ch;
  433.             openmen = op;
  434.             points = pt;
  435.             endman = em;
  436.             barmen = abs(board[home]);
  437.             oldfrc = frc;
  438.             oldfrp = frp;
  439.         }
  440.         menin = *inptr;
  441.         menoff = *offptr;
  442.     }
  443. #ifdef DEBUG
  444.     else  {
  445.         fprintf (trace,"\t[%s] ... loses.\n",tests);
  446.         fflush (trace);
  447.     }
  448. #endif
  449. }
  450.  
  451. movegood ()  {
  452.     register int    n;
  453.  
  454.     if (*offptr == 15)
  455.         return (1);
  456.     if (menoff == 15)
  457.         return (0);
  458.     if (race)  {
  459. #ifdef DEBUG
  460.         strcat (tests,"o");
  461. #endif
  462.         if (*offptr-menoff)
  463.             return (*offptr > menoff);
  464. #ifdef DEBUG
  465.         strcat (tests,"e");
  466. #endif
  467.         if (endman-em)
  468.             return (endman > em);
  469. #ifdef DEBUG
  470.         strcat (tests,"i");
  471. #endif
  472.         if (menin == 15)
  473.             return (0);
  474.         if (*inptr == 15)
  475.             return (1);
  476. #ifdef DEBUG
  477.         strcat (tests,"i");
  478. #endif
  479.         if (*inptr-menin)
  480.             return (*inptr > menin);
  481.         return (rnum(2));
  482.     } else  {
  483.         n = barmen-abs(board[home]);
  484. #ifdef DEBUG
  485.         strcat (tests,"c");
  486. #endif
  487.         if (abs(chance-ch)+25*n > rnum(150))
  488.             return (n? (n < 0): (ch < chance));
  489. #ifdef DEBUG
  490.         strcat (tests,"o");
  491. #endif
  492.         if (*offptr-menoff)
  493.             return (*offptr > menoff);
  494. #ifdef DEBUG
  495.         strcat (tests,"o");
  496. #endif
  497.         if (abs(openmen-op) > 7+rnum(12))
  498.             return (openmen > op);
  499. #ifdef DEBUG
  500.         strcat (tests,"b");
  501. #endif
  502.         if (n)
  503.             return (n < 0);
  504. #ifdef DEBUG
  505.         strcat (tests,"e");
  506. #endif
  507.         if (abs(endman-em) > rnum(2))
  508.             return (endman > em);
  509. #ifdef DEBUG
  510.         strcat (tests,"f");
  511. #endif
  512.         if (abs(frc-oldfrc) > rnum(2))
  513.             return (frc < oldfrc);
  514. #ifdef DEBUG
  515.         strcat (tests,"p");
  516. #endif
  517.         if (abs(n = pt-points) > rnum(4))
  518.             return (n > 0);
  519. #ifdef DEBUG
  520.         strcat (tests,"i");
  521. #endif
  522.         if (*inptr-menin)
  523.             return (*inptr > menin);
  524. #ifdef DEBUG
  525.         strcat (tests,"f");
  526. #endif
  527.         if (abs(frp-oldfrp) > rnum(2))
  528.             return (frp > oldfrp);
  529.         return (rnum(2));
  530.     }
  531. }
  532.